package __回溯算法

/*
https://leetcode.cn/problems/combinations/

77. 组合
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。

示例 1：
输入：n = 4, k = 2
输出：
[

	[2,4],
	[3,4],
	[2,3],
	[1,2],
	[1,3],
	[1,4],

]

示例 2：
输入：n = 1, k = 1
输出：[[1]]
*/
var (
	path77 []int   //临时子数组结果
	res77  [][]int //总结果数组
)

func combine(n int, k int) [][]int {

	path77 = make([]int, 0)
	res77 = make([][]int, 0)

	dfs77(n, k, 1)
	return res77
}

func dfs77(n int, k int, start int) {
	if len(path77) == k { //说明已经满足了k个数的要求
		temp := make([]int, k)
		copy(temp, path77)
		res77 = append(res77, temp)
		return
	}

	for i := start; i <= n; i++ { //以当前起点参数开始, 进行组合结果
		if n-i+1 < k-len(path77) { //如果剩余字符的长度, 已经不够拼接path的长度了, 就直接回溯吧, 已经不可能凑成path了, 没有继续递归的必要了
			break
		}

		path77 = append(path77, i)
		dfs77(n, k, i+1)
		path77 = path77[:len(path77)-1] //剔除末尾元素, 进行下一轮拼接
	}
}
